package 栈与队列;

import java.util.Stack;

/**
 * 150. 逆波兰表达式求值
 *
 * 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
 * 请你计算该表达式。返回一个表示表达式值的整数。
 *
 * 思路： 使用栈来解决该题
 * 1、栈的使用：逆波兰表达式的计算非常适合用栈来实现。遍历表达式中的每个元素：
     * 如果当前元素是数字，将其压入栈中。
     * 如果当前元素是操作符（+, -, *, /），从栈中弹出两个操作数，进行相应的运算，然后将结果压回栈中。
 * 2：最终结果：遍历完所有元素后，栈中剩下的唯一元素就是表达式的计算结果。
 */
public class L_150 {

    public int evalRPN(String[] tokens) {
        Stack<Integer> numberStack = new Stack<>();
        for (String token : tokens){
            // 如果是操作符，则进行相应的运算
            if(isOperator(token)){
                Integer num1 = numberStack.pop();
                Integer num2 = numberStack.pop();
                int calculate = calculate(num2, num1, token);
                numberStack.push(calculate);
            }else { // 如果是数字，则直接入栈
                numberStack.push(Integer.parseInt(token));
            }
        }
        return numberStack.pop();
    }

    // 判断是否为操作符
    private boolean isOperator(String val){
        return val.equals("+") || val.equals("-") || val.equals("*") || val.equals("/");
    }

    // 计算两个数字的运算结果
    private int calculate(int num1, int num2, String operator){
        switch (operator){
            case "+":
                return num1 + num2;
            case "-":
                return num1 - num2;
            case "*":
                return num1 * num2;
            case "/":
                return num1 / num2;
            default:
                throw new IllegalArgumentException("Invalid operator: " + operator);
        }
    }
}
